package com.example.leetcode.prcatice;

import java.util.HashMap;
import java.util.Map;

/**
 * 你可以搭配 任意 两道餐品做一顿大餐。
 *
 * <p>给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i​​​​​​​​​​​​​​ 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 大餐
 * 的数量。结果需要对 109 + 7 取余。
 *
 * <p>注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/count-good-meals
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test1711 {
 // 算出来，但超时了
    public int countPairs(int[] deliciousness) {
        int len = deliciousness.length;
        long ans = 0;
        int mod = (int)1e9+7;
        for (int i =0;i<len-1;i++){
            for (int j = i+1; j<len;j++){
                int re = deliciousness[i] + deliciousness[j];
                if(isTwo(re)){
                    ans++;
                }
            }
        }
        return (int)(ans % mod);
    }

    public boolean isTwo(int n){
        return n>0 && (n & (n -1)) == 0;
    }

    int mod = (int)1e9+7;
    int max = 1 << 22;
    // 时间未超过
    public int countPairs2(int[] ds) {
        Map<Integer, Integer> map = new HashMap<>();
        int ans = 0;
        for (int x : ds) {
            for (int i = 1; i < max; i <<= 1) {  // 遍历t和那些数字可以组成二次幂
                int t = i - x;
                if (map.containsKey(t)) {
                    ans += map.get(t);
                    if (ans >= mod) ans -= mod;
                }
            }
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        return ans;
    }

}

class Demo1711{
  public static void main(String[] args) {
    Test1711 t = new Test1711();
    int[] deliciousness = {1,3,5,7,9};
    System.out.println(t.countPairs(deliciousness));

  }
}